package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
 *
 *
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 *
 * 图示两个链表在节点 c1 开始相交：
 *
 *
 *
 * 题目数据 保证 整个链式结构中不存在环。
 *
 * 注意，函数返回结果后，链表必须 保持其原始结构 。
 *
 * @author hanjuntao
 * @date 2025/8/11 0011
 */
public class L_160_相交链表 {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(4);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(8);
        ListNode node4 = new ListNode(4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        ListNode node6 = new ListNode(5);
        ListNode node7 = new ListNode(0);
        ListNode node8 = new ListNode(9);

        node6.next = node7;
        node7.next = node8;
        node8.next = node2;

        ListNode result = getIntersectionNode(node1, node6);
        ListNode.print(result);
    }

    /**
     * 思路：
     * 从题意可知，链表相交的起始节点，就是两个链表末尾的节点相同，如果找到第一个相交点，则该节点就是相交的起始节点
     *
     * 现在的问题变为如何找到第一个相交点
     *
     * 可以获取两个链表的长度，然后让长的链表先走差值步数
     * 最后两个链表一齐走，碰到相交节点，则该节点就是相交的起始节点
     *
     *
     * @param headA
     * @param headB
     * @return
     */
    private static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int aLen = 0;
        int bLen = 0;

        ListNode currA = headA;
        while (currA != null) {
            aLen++;
            currA = currA.next;
        }

        ListNode currB = headB;
        while (currB != null) {
            bLen++;
            currB = currB.next;
        }

        currA = headA;
        if (aLen > bLen) {
            int count = Math.abs(aLen - bLen);
            while (count > 0) {
                currA = currA.next;
                count--;
            }
        }

        currB = headB;
        if (aLen < bLen) {
            int count = Math.abs(bLen - aLen);
            while (count > 0) {
                currB = currB.next;
                count--;
            }
        }

        // 最后两个链表一齐走，碰到相交节点，则该节点就是相交的起始节点
        while (currA != null && currB != null) {
            if (currA == currB) {
                return currA;
            }

            currA = currA.next;
            currB = currB.next;
        }

        return null;
    }
}
